class Solution(object):
    def findDuplicate(self, nums):
        """
        给定一个长度为n+1的数组，所有的数字均在1-n之间，一定存在重复多次的整数，
        本题给定只存在一个重复多次的整数，试找出它，要求时间复杂度O(n^2)以下，
        空间复杂度为O(1)
        """
        """ 
        1.数组中有一个重复的整数 <==> 链表中存在环加上一个链
        2.找到数组中的重复整数 <==> 找到链表的环入口
        假设环的周长为b,慢的指针在环内要落后快指针b步，原本同时从环上
        某一点出发，则再次相遇也是在这一点，而在环外也要落后a步，因此相遇地点要往前移动a步
        所以，从链的端点到环的入口，以及快满指针相遇地点到环的入口步数相同
        """
        """
        很多题解没有讲清楚非环部分的长度与相遇点到环起点那部分环之间为何是相等的这个数学关系。这里我就补充下为何他们是相等的。
        假设非环部分的长度是x，从环起点到相遇点的长度是y。环的长度是c。
        现在走的慢的那个指针走过的长度肯定是x+n1*c+y，走的快的那个指针的速度是走的慢的那个指针速度的两倍。这意味着走的快的那个指针走的长度是2(x+n1*c+y)。
        还有一个约束就是走的快的那个指针比走的慢的那个指针多走的路程一定是环长度的整数倍。根据上面那个式子可以知道2(x+n1*c+y)-x+n1*c+y=x+n1*c+y=n2*c。
        所以有x+y=(n2-n1)*c,这意味着什么？我们解读下这个数学公式：非环部分的长度+环起点到相遇点之间的长度就是环的整数倍。这在数据结构上的意义是什么？现在我们知道两个指针都在离环起点距离是y的那个相遇点，而现在x+y是环长度的整数倍，这意味着他们从相遇点再走x距离就刚刚走了很多圈，这意味着他们如果从相遇点再走x就到了起点。
        那怎么才能再走x步呢？答：让一个指针从头部开始走，另一个指针从相遇点走，等这两个指针相遇那就走了x步此时就是环的起点。
        """
        """ 
        这个题目按照这个解法有一点点的小问题，也就是将所有的下标和数组的内容都看成是
        图的一个顶点的话，那么假如该图不是连通的，就可能无法找到重复数字了
        """
        fast, slow = 0, 0
        while True:
            fast = nums[nums[fast]]
            slow = nums[slow]
            if fast == slow:
                break
        finder = 0
        while True:
            finder=nums[finder]
            slow=nums[slow]
            if finder==slow:
                return finder

if __name__ == '__main__':
    s = Solution()
    nums = [1, 0, 2, 3, 3]
    print(s.findDuplicate(nums))
